package ali;

/**
 *
 * @author wxh
 */
public class Solution_23 {

	/**
	 * 中心扩散法
	 */
	private String result = "";
	public String longestPalindrome(String s) {
		int len = s.length();
		if (len < 2) {
			return s;
		}

		for (int i = 0; i < len; i++) {
			// 如果回文子串长度是奇数,最中间是同一个数,所以取一个就行
			checkPalindrome(i, i, s);
			// 如果回文子串长度是偶数,取两个数字
			checkPalindrome(i, i + 1, s);
		}

		return result;
	}

	private void checkPalindrome(int start, int end, String s) {

		// 符合回文条件，则往两边扩散
		while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
			start--;
			end++;
		}

		// 此处start,end的值循环完后，是恰好不满足循环条件的时刻
		// 所以此时start到end的距离为：end - start + 1
		// 但是start,end的两个边界不能取，所以应该取start+1到end-1的区间  所以实际的长度是：end-start-1
		if (end - start - 1 > result.length()) {
			//substring要取[m+1,n-1]这个区间
			//end处的值不取,所以下面写的是n不是n-1
			result = s.substring(start + 1, end);
		}
	}

}